package middle;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution_149 {

    private Map<String, Set<Integer>> map = new HashMap<>();
    private String format = "%d:%d:%d";

    public int maxPoints(int[][] points) {
        map.clear();
        Arrays.sort(points, Comparator.comparingInt(o -> o[0]));
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                String format;
                if (points[i][0] == points[j][0]) {
                    format = String.format(this.format, 1, 0, points[i][0]);
                } else {
                    int a = points[i][1] - points[j][1];
                    if (a < 0) {
                        System.out.println();
                    }
                    int b = points[j][0] - points[i][0];
                    int c = points[i][0] * points[j][1] - points[j][0] * points[i][1];
//                    int divide = handle(a , b, c);
                    int max = Math.max(a, Math.max(b, c));
                    int divide = 1;
                    for (int mod = max; mod > 0; mod--) {
                        if (a % mod == 0 && b % mod == 0 && c % mod == 0) {
                            divide = mod;
                            break;
                        }
                    }

                    format = String.format(this.format, a / divide, b / divide, c / divide);
                }
                Set<Integer> set = map.getOrDefault(format, new HashSet<>());
                set.add(i);
                set.add(j);
                map.put(format, set);
            }
        }
        int count = 1;
        for (Set<Integer> value : map.values()) {
            count = Math.max(value.size(), count);
        }
        return count;
    }

    private int handle(int a, int b, int c) {
        if ((a == 0 && b == 0) || (a == 0 && c == 0) || (b == 0 && c == 0)) {
            return 1;
        } else if (a == 0) {
            return gys(b, c);
        } else if (b == 0) {
            return gys(a, c);
        } else if (c == 0) {
            return gys(a, b);
        } else {
            return Math.min(gys(a, b), Math.min(gys(b, c), gys(a, c)));
        }
    }

    private int gys(int m, int n) {
        if (m > n) {
            return gys(n, m);
        }

        while (m != 0) {
            if (n % m == 0) {
                return m;
            }
            int mod = n%m;
            n = m;
            m = mod;
        }
        return 1;
    }

    public static void main(String[] args) {
        Solution_149 model = new Solution_149();
        System.out.println(model.maxPoints(new int[][]{{7,3},{19,19},{-16,3},{13,17},{-18,1},{-18,-17},{13,-3},{3,7},{-11,12},{7,19},{19,-12},{20,-18},{-16,-15},{-10,-15},{-16,-18},{-14,-1},{18,10},{-13,8},{7,-5},{-4,-9},{-11,2},{-9,-9},{-5,-16},{10,14},{-3,4},{1,-20},{2,16},{0,14},{-14,5},{15,-11},{3,11},{11,-10},{-1,-7},{16,7},{1,-11},{-8,-3},{1,-6},{19,7},{3,6},{-1,-2},{7,-3},{-6,-8},{7,1},{-15,12},{-17,9},{19,-9},{1,0},{9,-10},{6,20},{-12,-4},{-16,-17},{14,3},{0,-1},{-18,9},{-15,15},{-3,-15},{-5,20},{15,-14},{9,-17},{10,-14},{-7,-11},{14,9},{1,-1},{15,12},{-5,-1},{-17,-5},{15,-2},{-12,11},{19,-18},{8,7},{-5,-3},{-17,-1},{-18,13},{15,-3},{4,18},{-14,-15},{15,8},{-18,-12},{-15,19},{-9,16},{-9,14},{-12,-14},{-2,-20},{-3,-13},{10,-7},{-2,-10},{9,10},{-1,7},{-17,-6},{-15,20},{5,-17},{6,-6},{-11,-8}}));
//        System.out.println(model.maxPoints(new int[][]{{0,0},{2,2},{-1,-1}}));
//        System.out.println(model.maxPoints(new int[][]{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}));
//        System.out.println(model.maxPoints(new int[][]{{1, 1}, {2, 2}, {3, 3}}));
    }
}
